#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    private:
    TreeNode* father;

    public:
    TreeNode* ans1(TreeNode* root, TreeNode* p, TreeNode* q){
        frontorder(root, p, q);

        return father;
    }

    bool frontorder(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root == nullptr){
            return false;
        }
        
        bool lson = frontorder(root->left, p, q);
        bool rson = frontorder(root->right, p, q);

        if((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))){
            father = root;
        }

        return lson || rson || (root->val== p->val || root->val == q->val);
    }

};

TreeNode* createTree(vector<int>& num, int index, int len){
    if(num[index] == '#'){
        return NULL;
    }
    TreeNode* root = new TreeNode(num[index]);

    if(index * 2 + 1 < len){
        root->left = createTree(num, index * 2 + 1, len);
    }else{
        root->left = nullptr;
    }
    if(index * 2 + 2 < len){
        root->right = createTree(num, index * 2 + 2, len);
    }else{
        root->right = nullptr;
    }

    return root;
    }

void test1(){
    vector<int> num = {3,5,1,6,2,0,8,'#','#',7,4};
    TreeNode* root = createTree(num, 0, num.size());
    TreeNode* p = new TreeNode(5);
    TreeNode* q = new TreeNode(1);

    Solution s;
    TreeNode* ret = s.ans1(root, p, q);
    cout << ret->val << endl;
    
}

void test2(){
    vector<int> num = {3,5,1,6,2,0,8,'#','#',7,4};
    TreeNode* root = createTree(num, 0, num.size());
    TreeNode* p = new TreeNode(5);
    TreeNode* q = new TreeNode(4);

    Solution s;
    TreeNode* ret = s.ans1(root, p, q);
    cout << ret->val << endl;
    
}


int main(void){
    test1();
    test2();

    return 0;
}